#include<stdio.h>
#include<stdlib.h>
#include <string.h>

#define XALLOC(type,size) (type *)malloc(size*sizeof(type))
#define XMEMSET(pointer,type,num) memset(pointer,0,num*sizeof(type))

/*
_In: pointer and type
_Out: pointer with memory allocate
*/
#define CreateOne(pointer,type) \
	do		\
	{		\
		pointer = (type *)malloc(sizeof(type));\
		memset(pointer,0,sizeof(type));\
	}while(0)\

typedef struct treeNode
{
	struct treeNode *left;
	struct treeNode *right;
	struct treeNode *parent;
	int node;
}TreeNode;

typedef struct queue
{
	struct queue *next;
	struct queue *prev;
	TreeNode *node;
}Queue;

void Enqueue(Queue *q,Queue *node)
{
	Queue *t = q;
	do 
	{
		if(t->next!=NULL)
			t=t->next;
		else
			break;
	} while (1);

	t->next = node;
	node->prev = t;
	node->next = NULL;
}

Queue* Dequeue(Queue *q)
{
	Queue *t = q;
	q=q->next;
	q->prev =NULL;
	t->next=NULL;
	return t;
}

void AssignNode(TreeNode *node,int content)
{
	node->node = content;
	node->right = NULL;
	node->left = NULL;
	node->parent = NULL;
}

void BuildTree(TreeNode *node,int content)
{
	if(node != NULL)
	{
		if(node->node>content)
		{
			if(node->left!=NULL)
				BuildTree(node->left,content);
			else
			{
				node->left = XALLOC(TreeNode,1);
				AssignNode(node->left,content);
				node->left->parent = node;
			}
		}
		else
		{
			if(node->right!=NULL)
				BuildTree(node->right,content);
			else
			{
				node->right = XALLOC(TreeNode,1);
				AssignNode(node->right,content);
				node->right->parent = node;
			}
		}
	}
}

void DumpTree(TreeNode *root)
{
	if(root!=NULL)
	{
		DumpTree(root->left);
		printf("%d\t",root->node);
		DumpTree(root->right);
	}
}

void DumpTreeByLevel(TreeNode *root)
{
	Queue *q;
	CreateOne(q,Queue);
	q->node = root;

}

TreeNode* MaxNode(TreeNode *root)
{
	if(root->right==NULL)
	{
		printf("%d\n",root->node);
		return root;
	}

	if(root->right!=NULL)
	{
		MaxNode(root->right);
	}
}

TreeNode* MinNode(TreeNode *root)
{
	if(root->left == NULL)
	{
		printf("%d\n",root->node);
		return root;
	}

	if(root->left!=NULL)
	{
		MinNode(root->left);
	}
}

TreeNode* SearchNode(TreeNode* root,int target)
{
	if(root->node == target)
	{
		return root;
	}

	if(root->node>target)
	{
		if(root->left!=NULL)
		{
			return SearchNode(root->left,target);
		}
		else
			return NULL;
	}

	if(root->node<target)
	{
		if(root->right!=NULL)
		{
			return SearchNode(root->right,target);
		}
		else
			return NULL;
	}

	return NULL;
}

TreeNode *TreeSuccessor(TreeNode *root)
{
	return MinNode(root->right);
}

TreeNode *TreePreccessor(TreeNode *root)
{
	return MaxNode(root->left);
}

void DeleteNode(TreeNode* root,int target)
{
	TreeNode* targetNode = SearchNode(root,target);
	if(targetNode != NULL)
	{
		TreeNode* pointNode; //Point to Delete Node
		if(targetNode->left == NULL || targetNode->right == NULL)
		{
			pointNode = targetNode;
		}
		else
			pointNode = TreeSuccessor(targetNode);

		//pointNode points to the node to be deleted.
		/*If pointNode is not the node we want to delete, we need to move the 
		* successor, so we need to delete the successor as well.
		*/
		TreeNode *nextNode;
		if(pointNode->left != NULL)
		{
			nextNode= pointNode->left;
		}
		else
		{
			nextNode = pointNode->right;
		}

		if (nextNode != NULL)
		{
			nextNode->parent = pointNode->parent;
		}

		if(pointNode->parent==NULL)
		{
			root->node = nextNode->node;
		}
		else
		{
			if(pointNode->parent->left == pointNode)
			{
				pointNode->parent->left = nextNode;
			}

			if(pointNode->parent->right == pointNode)
			{
				pointNode->parent->right = nextNode;
			}
		}

		if(targetNode != pointNode)
		{
			targetNode->node = pointNode->node;
		}
	}
	else
		printf("The node does not exists\n");
}
 /*  
                P 
                | 
             +-----+
             |  x  |
             +-----+
              /  \  
             /    \ 
            @       +-----+    
                    |  y  | 
                    +-----+                    
                     /  \
                    /    \
                    B     R     
                    
                    
                    
                   P     
                   |
                +-----+             
                |  y  |                         
                +-----+                         
                /     \
               /       \
        +-----+         R   
        |  x  |                         
        +-----+                         
        /     \                        
       /       \
      @         B
*/
void LeftRotate(TreeNode *root,TreeNode *x)
{
	TreeNode *y = x->right;
	x->right = y->left;
	y->left->parent = x;
	y->parent = x->parent;

	if(x->parent == NULL)
	{
		root=y;
	}
	else if(x== x->parent->left)
	{
		x->parent->left = y;
	}
	else if(x==x->parent->right)
	{
		x->parent->right = y;
	}

	y->left = x;
	x->parent = y;
}

/*
                   P     
                   |
                +-----+             
                |  y  |                         
                +-----+                         
                /     \
               /       \
        +-----+         R   
        |  x  |                         
        +-----+                         
        /     \                        
       /       \
      @         B

      
 
                P 
                | 
             +-----+
             |  x  |
             +-----+
              /  \  
             /    \ 
            @       +-----+    
                    |  y  | 
                    +-----+                    
                     /  \
                    /    \
                    B     R     
                 
*/

void RightRotate(TreeNode *root,TreeNode *y)
{
	TreeNode *x = y->left;
	y->left = x->right;
	x->right->parent = y;
	x->parent = y->parent;

	if(y->parent == NULL)
	{
		root=x;
	}
	else if(y == y->parent->left)
	{
		y->parent->left = x;
	}
	else if(y == y->parent->right)
	{
		y->parent->right = x;
	}
	
	x->right = y;
	y->parent = x;
}

int main() 
{
	int a[9]={1, 4, 5, 10, 16, 17, 21,-3,-1};
	int i;

	TreeNode *root= XALLOC(TreeNode,1);
	AssignNode(root,a[0]);

	for(i=1;i<9;i++)
	{
		BuildTree(root,a[i]);
	}

	DumpTree(root);

	printf("\n");
	MaxNode(root);
	printf("\n");
	MinNode(root);
	printf("\n");

	TreeNode *result = SearchNode(root,5);

	if(result!=NULL)
	{
		printf("%d exists",result->node);
	}

	printf("\n");
	printf("\n");

	for(i=1;i<9;i++)
	{
		printf("Delete Node %d\n",a[i]);
		DeleteNode(root,a[i]);
		DumpTree(root);
		printf("Delete End!!\n");
	}

	return 0; 
} 
